import random
import math

def assign_cluster(x, c):
    """
    将样本x分配到最近的簇中心
    
    参数:
        x: 单个样本向量 (list 或 tuple)
        c: 簇中心列表，每个元素是一个簇中心向量 (list of lists)
    
    返回:
        int: 最近簇的索引
    """
    min_distance = float('inf')
    cluster_index = 0
    
    for i, center in enumerate(c):
        # 计算欧几里得距离
        distance = 0.0
        for xi, ci in zip(x, center):
            distance += (xi - ci) ** 2
        distance = math.sqrt(distance)
        
        # 更新最近簇
        if distance < min_distance:
            min_distance = distance
            cluster_index = i
    
    return cluster_index

def Kmeans(data, k, epsilon=1e-6, iteration=100):
    """
    K 均值聚类算法实现
    
    参数:
        data: 样本集，每个元素是一个样本向量 (list of lists)
        k: 簇的数量 (int)
        epsilon: 簇中心变化的阈值，用于判断收敛 (float, 可选)
        iteration: 最大迭代次数 (int, 可选)
    
    返回:
        tuple: (簇分配结果, 最终簇中心)
            - 簇分配结果: list，每个元素是对应样本的簇索引
            - 最终簇中心: list of lists，每个元素是一个簇中心向量
    """
    # 检查输入有效性
    if not data or k <= 0 or k > len(data):
        raise ValueError("无效的输入参数")
    
    # 1. 初始化簇中心：随机选择 k 个样本作为初始中心
    num_samples = len(data)
    num_features = len(data[0])
    cluster_centers = random.sample(data, k)
    
    for _ in range(iteration):
        # 2. 分配簇
        cluster_assignments = [assign_cluster(x, cluster_centers) for x in data]
        
        # 3. 更新簇中心
        new_cluster_centers = []
        for i in range(k):
            # 收集当前簇的所有样本
            cluster_samples = [data[j] for j in range(num_samples) if cluster_assignments[j] == i]
            
            # 计算新的簇中心（均值）
            if not cluster_samples:  # 避免空簇
                new_center = random.choice(data)  # 重新随机选择一个中心
            else:
                new_center = []
                for f in range(num_features):
                    feature_mean = sum(sample[f] for sample in cluster_samples) / len(cluster_samples)
                    new_center.append(feature_mean)
            
            new_cluster_centers.append(new_center)
        
        # 4. 检查收敛：计算簇中心的总变化量
        total_change = 0.0
        for old_center, new_center in zip(cluster_centers, new_cluster_centers):
            for old, new in zip(old_center, new_center):
                total_change += (old - new) ** 2
        
        # 如果变化量小于阈值，收敛并退出
        if math.sqrt(total_change) < epsilon:
            break
        
        cluster_centers = new_cluster_centers
    
    return cluster_assignments, cluster_centers